import java.util.*;

public class Solution315 {

    static class BIT{

        int[] h;
        int n;

        public BIT(int n){
            h=new int[n+1];
            this.n=n;
        }

        private int lowBit(int x){
            return x&(-x);
        }

        public void update(int k){
            while (k<=n){
                h[k]+=1;
                k+=lowBit(k);
            }
        }

        public int query(int k){
            int t=0;
            while (k>0){
                t+=h[k];
                k-=lowBit(k);
            }
            return t;
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        TreeSet<Integer> set=new TreeSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int id=0;
        Map<Integer,Integer> map=new HashMap<>();
        for (Integer integer : set) {
            id++;
            map.put(integer,id);
        }
        List<Integer> ans=new ArrayList<>();
        BIT bit=new BIT(id);
        for (int i=nums.length-1;i>=0;i--){
            ans.add(0,bit.query(map.get(nums[i])-1));
            bit.update(map.get(nums[i]));
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution315().countSmaller(new int[]{5,2,6,1}));
    }
}
